/*
* 二叉树后序遍历非递归（利用栈）
*https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/
* */
class PostorderTraversalNotDiGui {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode node=root;
        TreeNode pre=null;
        while(!stack.isEmpty()||node!=null){
            while(node!=null){
                stack.push(node);
                node=node.left;
            }
            node=stack.pop();
            if(node.right==null||node.right==pre){
                ret.add(node.val);
                pre=node;
                node=null;
            }else{
                stack.push(node);
                node=node.right;
            }
        }
        return ret;
    }
}